The present invention relates to the fast processing of electronic signals and, more particularly, to the fast processing of signals in a positioning system based on a satellite network such as the Global Positioning System (GPS).
The Global Positioning System is a constellation of Earth-orbiting satellites that transmit standard signals that can be used to establish the location and velocity of a user equipped with a suitable GPS receiver. For civilian applications, the basic signals are xe2x80x9cC/A codesxe2x80x9d or Gold Codes, pseudo-random noise (PN) sequences, transmitted as repeated frames of 1023 chips at a chip rate of 1023 chips/ms (xe2x89xa1one frame per millisecond). Each satellite is assigned a unique PN sequence, the PN sequences of the various satellites being mutually orthogonal.
Superimposed on the PN sequence of each GPS satellite is a continuously repeating Satellite Data Message (SDM), of 30 seconds duration, transmitted at a rate of 50 bits per second. The complete SDM is therefore 1500 bits long. Each bit (+1 or xe2x88x921) of the SDM is modulated onto the satellite""s signal by multiplying 20 consecutive frames of the PN sequence by that bit. The first 900 bits of the SDM include the satellite ephemeris and time model for the respective satellite. The remaining 600 bits of the SDM include a portion of the GPS almanac, which is a 15,000 bit block of coarse ephemeris and time model data for the entire GPS system. In addition, bits 1-8, bits 301-308, bits 601-608, bits 901-908 and bits 1201-1208 of every SDM are identical 8-bit (160 millisecond) headers that are invariant in time and that are identical in all the GPS satellites. Bits 31-60 , bits 331-360, bits 631-660, bits 931-960 and bits 1231-1260 of every SDM are 30-bit (600 millisecond) hand-over words that are time-variant (these hand-over words include representations of the time of the week), but are, like the headers, identical in all the GPS satellites.
A GPS mobile unit receives a signal as a function of time, t, of the form:       G    ⁡          (      t      )        =            ∑      j        ⁢                  G        j            ⁡              (        t        )            
where:
Gj(t)=KjDj(txe2x88x92xcfx84j)gj(txe2x88x92xcfx84j) exp [ixcfx89(txe2x88x92xcfx84j)], 
is the signal received from satellite j,j being an index that denotes a single satellite of those that are visible; i is the square root of xe2x88x921; xcfx84j is the true one-way propagation time of radio waves from satellite j to the mobile unit; Kj is an amplitude factor that depends on the true range Rj=cxcfx84j to satellite j at time t, and on the GPS antenna-gain pattern; Dj(txe2x88x92xcfx84j) is the SDM of satellite j at time (txe2x88x92xcfx84j); gj(txe2x88x92xcfx84j) is the PN sequence of satellite j at time (txe2x88x92xcfx84j); and exp [ixcfx89j(txe2x88x92xcfx84j)] is a frequency factor whose Doppler shift depends on the radial component of the velocity of satellite j relative to the mobile unit, on the bias of the mobile unit""s internal clock, and on other imperfections in the mobile unit.
Conventionally, a GPS receiver acquires and tracks the signals from at least four GPS satellites by correlating the received signal with the satellites"" respective PN sequences and locking on to the correlation peaks. Once a satellite is acquired and tracked, the GPS receiver decodes the ephemeris and time model thereof, from the respective SDM. This is repeated for each required satellite: These models include sufficient ephemeris data to enable the GPS receiver to compute the satellitesxe2x80x2 positions. The correlation peaks obtained during the continued tracking of the satellites provide measured times of arrival of these PN sequence frames. The differences between an arbitrary reference time and measured times of arrival, multiplied by the speed of light, are pseudo-ranges xcfx81j from the satellites to the GPS receiver. Typically, the reference time is the time at which the satellites commenced transmission of their respective PN sequences, as measured by the GPS receiver clock, which in general is offset from the GPS system clock by an unknown time offset. A pseudo-range, xcfx81, is related to the true range, R, of the respective satellite by xcfx81=R+cb, where the range offset cb is the time offset, T0, of the GPS receiver relative to GPS system time, multiplied by the speed of light c: cb=T0c. From these pseudo-ranges, and from the known positions of the satellites as functions of time, the position of the GPS receiver is calculated by triangulation. Pseudo-ranges to at least four satellites are needed to solve at least four simultaneous equations of the form:
xe2x80x83|{right arrow over (s)}xe2x88x92{right arrow over (r)}|=xcfx81xe2x88x92cb
where {right arrow over (s)} is the position vector of a satellite and {right arrow over (r)}=(x,y,z) is the position vector of the GPS receiver, for the three unknown Cartesian coordinates x, y, z of the GPS receiver and for cb. The satellites are sufficiently far from the GPS receiver that these equations can be linearized in x, y, and z with no loss of accuracy.
In similar fashion, measurement of the Doppler shifts of the received satellite signals enables calculation of the velocity of the GPS receiver. At least four simultaneous equations of the form:
({right arrow over (xcexd)}sxe2x88x92{right arrow over (xcexd)})xc2x7LOS=xcexdrxe2x88x92cd
where {right arrow over (xcexd)}s is actual satellite velocity, {right arrow over (xcexd)} is velocity of the mobile unit, LOS is a unit vector denoting the line of sight to an observed GPS satellite, and cd is a clock drift correction. Relative speed with respect to a satellite is calculated from a measurement of the respective Doppler shift in the signal from that satellite.
A number of patents (e.g. U.S. Pat. No. 5,781,156) describe GPS receivers operating in a snapshot method. Such receivers record a sample of the signal from GPS satellites and process the recording later, off-line. This enables high reception sensitivity, as well as low consumption of battery power and small physical size. Signal processing must, however, be highly efficient in order to save processing time. Some of these receivers achieve a significant saving in processing time by transferring ancillary data for processing elsewhere through a communications network (cellular or other), in which case it is still important to reduce the amount of ancillary data sent, in order to save on communications resources.
Several prior art methods are known for increasing the efficiency with which a GPS receiver establishes its position and for reducing the power requirements of a GPS receiver. The SDM is 30 seconds long so, even under ideal reception conditions with parallel processing of the signals from all the satellites in view, it necessarily takes more than 30 seconds to get a GPS position fix. Prior knowledge of the SDM can reduce this time to less than 10 seconds. Schuchman et al., in U.S. Pat. No. 5,365,450, which is incorporated by reference for all purposes as if fully set forth herein, teach the transmitting of the SDMs to a GPS receiver integrated into a mobile unit, such as a cellular telephone or other wireless communications network receiver, by a base station of the network via the control channel of the network.
Krasner, in U.S. Pat. No. 5,663,734, which is incorporated by reference for all purposes as if fully set forth herein, teaches a GPS receiver for a mobile unit in which, as in the GPS receiver of Schuchman et al., the SDM is obtained via a wireless link to a base station, but then, instead of processing GPS signals in real time, the GPS receiver stores up to one second""s worth of signals (1000 PN sequence frames per satellite), along with the initial time of arrival (TOA) of the signals, and processes the stored signals. Groups of 5 to 10 frames each are summed and correlated with the PN sequences of satellites expected to be in view, and the resulting correlation functions are added incoherently. Summation over up to 1000 frames boosts the signal-to-noise ratio correspondingly, and the post facto processing requires much less power than real-time processing.
Whatever system is used, there is thus a widely recognized need for, and it would be highly advantageous to have, a signal-processing algorithm that reduces calculation time and resource use. A particularly efficient algorithm is disclosed hereunder, which makes it possible to obtain very high sensitivity while making minimal use of processing time and communications resources.
According to the present invention there is provided a method for fast processing of electronic signals for determining a location of a mobile receiver including the steps of: (a) providing a satellite-based positioning system including a plurality of satellites, each satellite transmitting a signal including a plurality of blocks, each block including a plurality of frames of a known pseudo-noise sequence unique to each satellite, each block being multiplied by a bit of a data sequence, the signal being frequency-shifted relative to a nominal frequency; (b) receiving, by the mobile receiver, a snapshot of the signals of all the satellites in view and arranging the snapshot in a two dimensional matrix; and (c) mathematically windowing and transforming the matrix.
Preferably, the method of the invention further includes, for each satellite in view, the steps of: (i) selecting a portion of the mathematically windowed and transformed matrix containing a preponderance of the signal of each satellite according to the expected Doppler shift of the signal, that portion being a matrix having as many rows and, at most, as many columns as the mathematically windowed and transformed matrix; (ii) preparing a reference vector corresponding to each satellite, the vector being a mathematically transformed copy of a frame of the known pseudo-noise sequence of each satellite and having a number of elements equal to a number of elements of the number of rows of the mathematically windowed and transformed matrix; (iii) multiplying respective elements of each column of the selected portion of the mathematically windowed and transformed matrix by respective elements of the reference vector, thereby producing an adjusted matrix; and (iv) performing an inverse discrete orthogonal transform on each row of the adjusted matrix.
Preferably, the method of the present invention includes the further steps of (v) isolating a desired signal event by demodulating the data sequence of each satellite, and (vi) deducing a time of arrival of that signal event and the Doppler shift of that signal from each satellite.
The method of the invention preferably requires at least four satellites to be in view.
Preferably, a subsequent step of the method of the invention includes providing the deduced times of arrival and Doppler shifts for all satellites in view for calculation of the location and velocity of the mobile receiver.
Preferably, the invention provides for the inclusion of an ancillary communications network transmitting a synchronization signal at a respective transmission frequency receivable by the mobile receiver.
According to the present invention, arranging the snapshot in a two-dimensional matrix preferably includes the steps of: (i) digitizing the snapshot, to produce a digitized signal including a plurality of digitized elements; and (ii) arranging the digitized elements consecutively by column in a two-dimensional matrix, each column containing a sub-plurality of elements and corresponding to an integral number of frames of the pseudo-noise sequence.
In a preferred embodiment of the present invention, the number of the sub-plurality of elements is a power of two.
In a preferred embodiment of the present invention, the integral number of frames is one.
In a preferred embodiment of the present invention, the elements are complex numbers whose components most preferably are stored either as two-bit numbers or as one-bit numbers.
According to the present invention, mathematically windowing and transforming the matrix into the frequency domain preferably includes the steps of (i) applying a window function to each row of the matrix, (ii) performing a two-dimensional discrete orthogonal transform on the matrix, and (iii) overwriting the original matrix with the transformed matrix. Most preferably, the window function is a Hamming window and the orthogonal transform is a Fourier transform.
According to the present invention, the method of selecting the portion of the mathematically transformed matrix containing a preponderance of the signal of the each satellite preferably is based on: (i) information related to the data sequence including the satellite transmission schedule and the trajectory parameters of each satellite, and (ii) the approximate location of the mobile receiver.
In a preferred embodiment of the present invention, the data sequence is obtained from a transmission by the corresponding satellite.
In a preferred embodiment of the present invention, the trajectory parameters are stored in and retrieved from a data bank, which may be located either with the mobile receiver or at an area server. In the latter case, the data bank is retrieved on demand via the ancilliary communications network.
Preferably, according to the present invention, the mathematical transformation of a frame of the pseudo-noise sequence includes the steps of: (A) mathematically resampling the frame to consist of a number of elements equal to the number of the sub-plurality of elements in a column of the adjusted matrix; (B) cyclically shifting the elements of the resampled frame to be in phase with the pseudo-noise sequence received from each satellite, in accordance with an estimate of the expected time of arrival of the pseudo-noise sequence and the drift of the local clock in the mobile receiver; (C) multiplying each element of the cyclically shifted frame by a respective Doppler compensation factor; (D) transforming the Doppler-compensated frame by means of a discrete orthogonal transform (most preferably a Fourier transform); and (E) replacing each element of the transformed frame by the complex conjugate thereof.
Preferably, the time of arrival is estimated from: (a) information related to the data sequence, including the satellite transmission schedule and trajectory parameters of each satellite, and (b) knowledge of the approximate location of the mobile receiver.
In one preferred embodiment of the present invention, the drift of the local clock is measured by (a) providing an ancillary communications network wherewith the mobile receiver communicates, the ancillary communications network transmitting a synchronization signal at a respective transmission frequency, and (b) calibrating the, local clock against the synchronization signal.
In another preferred embodiment of the present invention, the drift of the local clock is measured by: (a) providing an ancillary communications network wherewith the mobile receiver communicates, the ancillary communications network transmitting a synchronization signal at a respective transmission frequency, and (b) calibrating the local clock against the transmission frequency.
In yet another preferred embodiment of the present invention, the drift of the local clock is measured by comparison with the transmission frequency of each satellite.
In a preferred embodiment of the present invention, the Doppler compensation factors are based on the likely frequency shift of the signal of each satellite due to a Doppler effect arising from relative motion of the satellite with respect to the mobile receiver.
In a preferred embodiment of the present invention, the likely frequency shift is estimated from: (a) information related to the data sequence, including the satellite transmission schedule and trajectory parameters of each satellite, and (b) the approximate location and velocity of the mobile receiver.
Preferably; according to the present invention isolating the desired signal event includes the steps of: (i) selecting a contiguous sub-set of the rows of the inverse-transformed adjusted matrix, in accordance with an estimate of the likely presence therein of a preponderance of the signal event, thereby providing a reduced matrix having as many columns and, at most, as many rows as the inverse-transformed adjusted matrix; (ii) performing an inverse discrete orthogonal transform (most preferably an inverse Fourier transform) on each column of the reduced matrix; (iii) multiplying elements of columns of the inverted, reduced matrix by respective expected data-sequence bits; and (iv) performing a discrete orthogonal transform on each column of the multiplied, inverted, reduced matrix, resulting in a transformed, reduced matrix.
In a preferred embodiment of the present invention, the estimate of the likely presence therein of a preponderance of the signal event is derived from: (a) knowledge of the data sequence, (b) the satellite transmission schedule for the data sequence, (c) the trajectory parameters of each satellite; and (d) the approximate location of the mobile receiver.
Most preferably, the desired signal event is the start of a frame, of the pseudo-noise sequence.
According to one preferred embodiment of the present invention, the expected data-sequence bits are inferred from: (a) knowledge of the data sequence, (b) the satellite transmission schedule for the data sequence, (c) the trajectory parameters of each satellite, and (d) the approximate location of the mobile receiver.
According to another preferred embodiment of the present invention, the expected data sequence bits are hypothesized.
According to a preferred embodiment of the present invention, deducing the time of arrival of the signal event and the Doppler shift of the signal of each satellite is effected by steps including: (i) identifying at least one peak in the transformed, reduced matrix, each such peak having a row coordinate, a column coordinate, and an absolute magnitude, the row coordinate corresponding to a pseudo-range of each satellite and the column coordinate corresponding to the rate of change thereof and (ii) if a plurality of such peaks are identified, interpolating among the peaks to refine the identification of the row coordinate and the column coordinate.
Most preferably, the interpolation is effected by two-dimensional curve fitting or by one-dimensional curve-fitting in each of the row and column directions.